"""
# Definition for a Node.
"""
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random


class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        dic = {}
        if head is None:
            return None
        newHead = Node(head.val)
        tmp = head
        dic[head] = newHead
        while tmp:
            newTmp = dic[tmp]
            if tmp.next:
                if tmp.next not in dic.keys():
                    dic[tmp.next] = Node(tmp.next.val)
                newTmp.next = dic[tmp.next]
            if tmp.random:
                if tmp.random not in dic.keys():
                    dic[tmp.random] = Node(tmp.random.val)
                newTmp.random = dic[tmp.random]
            tmp = tmp.next

        return newHead


if __name__ == '__main__':
    so = Solution()
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)

    node1.next = node2
    node1.random = node2

    node2.next = None
    node2.random = node2

    re = so.copyRandomList(node1)
    print(re)
